Golden ratio base

Numeral systems by culture
Hindu-Arabic numerals
Western Arabic (Hindu numerals)
Eastern Arabic
Indian family
Tamil		 Burmese
Khmer
Lao
Mongolian
Thai
East Asian numerals
Chinese
Japanese
Suzhou		 Korean
Vietnamese
Counting rods
Alphabetic numerals
Abjad
Armenian
Āryabhaṭa
Cyrillic		 Ge'ez
Greek
Georgian
Hebrew
Other systems
Aegean
Attic
Babylonian
Brahmi
Egyptian
Etruscan
Inuit		 Kharosthi
Mayan
Quipu
Roman
Sumerian
Urnfield
List of numeral system topics
Positional systems by base
Decimal (10)
2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 20, 24, 30, 36, 60, 64
Non-positional system
Unary numeral system (Base 1)
List of numeral systems

Golden ratio base is a non-integer positional numeral system that uses the golden ratio (the irrational number (1+√5)/2 ≈ 1.61803399... symbolized by the Greek letter φ) as its base. It is sometimes referred to as base-φ, golden mean base, phi-base, or, colloquially, phinary. Any non-negative real number can be represented as a base-φ numeral using only the digits 0 and 1, and avoiding the digit sequence "11" - this is called a standard form. A base-φ numeral that includes the digit sequence "11" can always be rewritten in standard form, using the algebraic properties of the base φ — most notably that φ+1 = φ2. For instance, 11φ = 100φ.

Despite using an irrational number base, when using standard form, all non-negative integers have a unique representation as a terminating (finite) base-φ expansion. Other numbers have standard representations in base-φ, with rational numbers having recurring representations. These representations are unique, except that numbers with a terminating expansion also have a non-terminating expansion, as they do in base-10; for example, 1=0.99999….

Contents

Examples

Decimal Powers of φ Base φ
1 φ0 1     
2 φ1 + φ−2 10.01  
3 φ2 + φ−2 100.01  
4 φ2 + φ0 + φ−2 101.01  
5 φ3 + φ−1 + φ−4 1000.1001
6 φ3 + φ1 + φ−4 1010.0001
7 φ4 + φ−4 10000.0001
8 φ4 + φ0 + φ−4 10001.0001
9 φ4 + φ1 + φ−2 + φ−4 10010.0101
10 φ4 + φ2 + φ−2 + φ−4 10100.0101

Writing golden ratio base numbers in standard form

211.01φ is not a standard base-φ numeral, since it contains a "11" and a "2", which isn't a "0" or "1", and contains a 1=-1, which isn't a "0" or "1" either.

To "standardize" a numeral, we can use the following substitutions: 011φ = 100φ, 0200φ = 1001φ and 010φ = 101φ. We can apply the substitutions in any order we like, as the result is the same. Below, the substitutions used are on the right, the resulting number on the left.

  211.01φ
  300.01φ     011φ → 100φ
 1101.01φ     0200φ → 1001φ
10001.01φ     011φ → 100φ (again)
10001.101φ    010φ → 101φ
10000.011φ    010φ → 101φ (again)
10000.1φ      011φ → 100φ (again)

Any positive number with a non-standard terminating base-φ representation can be uniquely standardized in this manner. If we get to a point where all digits are "0" or "1", except for the first digit being negative, then the number is negative. This can be converted to the negative of a base-φ representation by negating every digit, standardizing the result, and then marking it as negative. For example, use a minus sign, or some other significance to denote negative numbers. If the arithmetic is being performed on a computer, an error message may be returned.

Note that when adding the digits "9" and "1", the result is a single digit "(10)", "A" or similar, as we are not working in decimal.

Representing integers as golden ratio base numbers

We can either consider our integer to be the (only) digit of a nonstandard base-φ numeral, and standardize it, or do the following:

1×1 = 1, φ × φ = 1 + φ and 1/φ = −1 + φ. Therefore, we can compute

(a + bφ) + (c + dφ) = ((a + c) + (b + d)φ),
(a + bφ) − (c + dφ) = ((a − c) + (b − d)φ)

and

(a + bφ) × (c + dφ) = ((ac + bd) + (ad + bc + bd)φ).

So, using integer values only, we can add, subtract and multiply numbers of the form (a + bφ), and even represent positive and negative integer powers of φ. (Note that φ−1 = 1/φ.)

(a + bφ) > (c + dφ) if and only if 2(a − c) − (d − b) > (d − b) × √5. If one side is negative, the other positive, the comparison is trivial. Otherwise, square both sides, to get an integer comparison, reversing the comparison direction if both sides were negative. On squaring both sides, the √5 is replaced with the integer 5.

So, using integer values only, we can also compare numbers of the form (a + bφ).

  1. To convert an integer x to a base-φ number, note that x = (x + 0φ).
  2. Subtract the highest power of φ, which is still smaller than the number we have, to get our new number, and record a "1" in the appropriate place in the resulting base-φ number.
  3. Unless our number is 0, go to step 2.
  4. Finished.

The above procedure will never result in the sequence "11", since 11φ = 100φ, so getting a "11" would mean we missed a "1" prior to the sequence "11".

Start, e. g., with integer=5, with the result so far being ...00000.00000...φ

Highest power of φ ≤ 5 is φ3 = 1 + 2φ ≈ 4.236067977

Subtracting this from 5, we have 5 - (1 + 2φ) = 4 − 2φ ≈ 0.763932023..., the result so far being 1000.00000...φ

Highest power of φ ≤ 4 − 2φ ≈ 0.763932023... is φ−1 = −1 + 1φ ≈ 0.618033989...

Subtracting this from 4 − 2φ ≈ 0.763932023..., we have 4 − 2φ − (−1 + 1φ) = 5 − 3φ ≈ 0.145898034..., the result so far being 1000.10000...φ

Highest power of φ ≤ 5 − 3φ ≈ 0.145898034... is φ−4 = 5 − 3φ ≈ 0.145898034...

Subtracting this from 5 − 3φ ≈ 0.145898034..., we have 5 − 3φ − (5 − 3φ) = 0 + 0φ = 0, with the final result being 1000.1001φ.

Non-uniqueness

Just as with any base-n system, numbers with a terminating representation have an alternative recurring representation. In base-10, this relies on the observation that 0.999...=1. In base-φ, the numeral 0.1010101... can be seen to be equal to 1 in several ways:

\sum_{k=0}^\infty \varphi^{-2k}=\frac{1}{1-\varphi^{-2}} = \varphi

This non-uniqueness is a feature of the numeration system, since both 1.0000 and 0.101010... are in standard form.

In general, the final 1 of any number in base-φ can be replaced with a recurring 01 without changing the value of that number.

Representing rational numbers as golden ratio base numbers

Every non-negative rational number can be represented as a recurring base-φ expansion, as can any non-negative element of the field Q[√5] = Q + √5Q, the field generated by the rational numbers and √5. Conversely any recurring (or terminating) base-φ expansion is a non-negative element of Q[√5]. Some examples (with spaces added for emphasis):

The justification that a rational gives a recurring expansion is analogous to the equivalent proof for a base-n numeration system (n=2,3,4,...). Essentially in base-φ long division there are only a finite number of possible remainders, and so once there must be a recurring pattern. For example with 1/2 = 1/10.01φ = 100φ/1001φ long division looks like this (note that base-φ subtraction may be hard to follow at first):

               .0 1 0 0 1
        ________________________
1 0 0 1 ) 1 0 0.0 0 0 0 0 0 0 0
            1 0 0 1                        trade: 10000 = 1100 = 1011
            -------                            so 10000-1001 = 1011-1001 = 10
                1 0 0 0 0
                  1 0 0 1
                  -------
                      etc.

The converse is also true, in that a number with a recurring base-φ; representation is an element of the field Q[√5]. This follows from the observation that a recurring representation with period k involves a geometric series with ratio φ-k, which will sum to an element of Q[√5].

Representing irrational numbers of note as golden ratio base numbers

The base-φ representations of some interesting numbers:

Addition, subtraction, and multiplication

It is possible to adapt all the standard algorithms of base-10 arithmetic to base-φ arithmetic. There are two approaches to this:

Calculate, then convert to standard form

For addition of two base-φ numbers, add each pair of digits, without carry, and then convert the numeral to standard form. For subtraction, subtract each pair of digits without borrow (borrow is a negative amount of carry), and then convert the numeral to standard form. For multiplication, multiply in the typical base-10 manner, without carry, then convert the numeral to standard form.

For example

Avoid digits other than 0 and 1

A more "native" approach is to avoid having to add digits 1+1 or to subtract 0-1. This is done by reorganising the operands into nonstandard form so that these combinations do not occur. For example

The subtraction seen here uses a modified form of the standard "trading" algorithm for subtraction.

Division

No non-integer rational number can be represented as a finite base-φ number. In other words, all finitely representable base-φ numbers are either integers or (more likely) an irrational in the field Q[√5]. Due to long division having only a finite number of possible remainders, a division of two integers (or other numbers with finite base-φ representation) will have a recurring expansion, as demonstrated above.

Relationship with Fibonacci coding

Main article: Fibonacci coding

Fibonacci coding is a closely related numeration system used for integers. In this system, only digits 0 and 1 are used and the place values of the digits are the Fibonacci numbers. As with base-φ, the digit sequence "11" is avoided by rearranging to a standard form, using the Fibonacci recurrence relation Fk+1 = Fk + Fk-1. For example

30 = 1×21 + 0×13 + 1×8 + 0×5 + 0×3 + 0×2 + 1×1 + 0×1 = 10100010fib.

See also

External links

References